import entity.TreeNode;

import java.util.Arrays;

public class MaximumBinaryTree {
    /*
    * 654. 最大二叉树
    * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
    * 创建一个根节点，其值为 nums 中的最大值。
    * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
    * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
    * 返回 nums 构建的 最大二叉树 。
    *
    * 1 <= nums.length <= 1000
    * 0 <= nums[i] <= 1000
    * nums 中的所有整数 互不相同
    * */
    public static void main(String[] args){
        MaximumBinaryTree o = new MaximumBinaryTree();
        o.mySolution(new int[]{3,2,1,6,0,5});
    }

    // 我的想法：题目已经给了要求，模拟就是了
    public TreeNode mySolution(int[] nums){
        return build(nums, 0, nums.length);
    }
    // 递归，区间左闭右开
    private TreeNode build(int[] nums, int start, int end){
        if(start >= end)    // 循环不变量，区间定义不变
            return null;
        // 这里判断是否为1可以节省时间
        if(end -start == 1)
            return new TreeNode(nums[start]);
        // 找出最大值
        int max = Integer.MIN_VALUE;
        int index = 0;
        for (int i = start; i < end; i++) {
            if(nums[i] > max){
                max = nums[i];
                index = i;
            }
        }
        // 构造节点
        TreeNode node = new TreeNode(max);
        // 左右切割
        node.left = build(nums, start, index);
        node.right = build(nums, index+1, end);
        return node;
    }
}
